package a00_LeetCode.Tree;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @Author quan
 * @Description 二叉树的完全性检验:给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。
 * @Date 2023/3/25 10:56
 */

/**
 * 根据完全二叉树的特向 ：如果完全二叉树中存在度为1的节点，有的话只有一个，没有则是没有。使用队列实现
 * 按照层序遍历的方式遍历二叉树：
 * Step1：当前每个节点都是度为2的节点；——>一旦遇见度为1的节点：分两种情况：
 * 如果该节点只有右孩子，直接false；①如果当前节点只存在左孩子，则转入Step2 || ②或者遇见第一个叶子节点转入Step2
 * Step2: 继续遍历从当前节点之后的每一个节点都必须为叶子结点，也就是当前完全二叉树全部为叶子结点
 * /**/
public class Num958_isCompleteTree {
     public boolean isCompleteTree(TreeNode root) {
         //按照层序遍历的方式遍历节点：创建一个队列，让root进队列
        Deque<TreeNode> deque = new LinkedList<>();
        deque.offer(root);
         boolean isStep1 = true;
        //当队列为空时层序遍历结束
         while (!deque.isEmpty()){
             //弹出元素记作node
             TreeNode node = deque.poll();
             //Step1:当每个节点都是度为2的节点时处在阶段1:当遇见度为1且存在的是左孩子 || 度为0的节点时
             if (isStep1){
                 if(node.left!=null && node.right!=null){//左右孩子都存在，则继续入队列
                     deque.offer(node.left);
                     deque.offer(node.right);
                 }
                 if(node.left==null && node.right!=null){//遇见度为1的节点且只有右孩子存在，则false
                     return false;
                 }
                 if(node.left!=null && node.right==null){//走到这里说明遇见度为1的节点，且存在的是左孩子或者是遇见的是叶子节点则转入阶段2
                     deque.offer(node.left);
                     isStep1 = false;
                 }
                 if(node.left==null && node.right==null){//遇见的是第一个叶子节点，则转入阶段2
                     isStep1 = false;
                 }
             }//走到这里说明是阶段2：判断当前的每一个节点都是叶子节点，如果不是则返回false
             else{
                 if( (node.left!=null || node.right!=null)){
                     return false;
                 }
             }
         }
         return true;
     }
}
